package com.wc.alorithm.string.suffixArray;

import java.util.Arrays;

/**
 * @Author congege
 * @Description
 * @Date Created in 2023/12/12-18:33
 */
public class Main {
    static int N = (int) (2e6 + 10);
    static char[] s = new char[N];
    static int[] buc = new int[N];
    static int[] sa = new int[N];
    // 复制上一次捅排序的结果
    static int[] sc = new int[N];
    static int[] rk = new int[N];
    static int[] height = new int[N];
    // 复制字符串，方便使用
    static int[] fr = new int[N];
    // n代表字符串长度+ 1, m 代表值域
    static int n, m = 122;

    private static void getSa() {
        // 计算第一个关键字符出现的次数
        for (int i = 1; i <= n; i++) {
            buc[fr[i] = s[i]]++;
        }
        // 计算前缀和
        for (int i = 1; i <= m; i++) {
            buc[i] += buc[i - 1];
        }
        // 后缀数组第一位置排序
        for (int i = n; i >= 1; i--) {
            sa[buc[fr[i]]--] = i;
        }

        // 倍增的框架
        for (int k = 1; k <= n; k <<= 1) {
            // 按照第二关键字进行排序
            // 清空桶
            Arrays.fill(buc, 0);

            // 将上一次的结果记录
            for (int i = 1; i <= n; i++) {
                sc[i] = sa[i];
            }
            // 统计第k关键关键字符出现次数
            for (int i = 1; i <= n; i++) {
                // k 第二位置排序，所以要+k
                buc[fr[sc[i] + k]]++;
            }
            // 前缀和
            for (int i = 1; i <= m; i++) {
                buc[i] += buc[i - 1];
            }
            // 后缀数组第位关键字排序
            for (int i = n; i >= 1; i--) {
                sa[buc[sc[i] + k]--] = sc[i];
            }
            Arrays.fill(buc, 0);

            // 按照第一关键字进行排序
            for (int i = 1; i <= n; i++) {
                sc[i] = sa[i];
            }
            // 统计第k关键关键字符出现次数
            for (int i = 1; i <= n; i++) {
                buc[fr[sc[i]]]++;
            }
            // 前缀和
            for (int i = 1; i <= m; i++) {
                buc[i] += buc[i - 1];
            }
            // 后缀数组第位关键字排序
            for (int i = n; i >= 1; i--) {
                sa[buc[sc[i]]--] = sc[i];
            }
            // 存桶
            for (int i = 1; i <= n; i++) {
                sc[i] = fr[i];
            }
            // 重新给桶编号
            m = 0;
            for (int i = 1; i <= n; i++) {
                if (sc[sa[i]] == sc[sa[i - 1]] && sc[sa[i] + k] == sc[sa[i - 1] + k]) {
                    fr[sa[i]] = m;
                } else {
                    fr[sa[i]] = ++m;
                }
            }
            // 当每一个已经在一个桶里面了,就不许要排序了，就可以结束了
            if (m == n) {
                break;
            }
        }
    }
}
